/* Copyright  2009
   @Author
   Richard Changde Yin            e-mail yinchangde@hotmail.com

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; version 2 of the License.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */

/**
 * @filename: treeIndex.cc
 */

#include <server_includes.h>
#include <allocator.h>
#include<index.h>
#include<catalogtables.h>
#include <database.h>
#include<lock.h>
#include<debug.h>
#include<table.h>

using namespace BackEnd ;

DbRetVal TreeIndex::insert(Table *tbl, Transaction *,
                           void *indexPtr, IndexInfo *indInfo,
                           void *tuple, bool )
{
    //printDebug(DM_TreeIndex, "\nInside TreeNode::Insert - 1");
    //HashIndexInfo *info = (HashIndexInfo*) indInfo;
    CINDEX *iptr = (CINDEX*)indexPtr;
    TreeNode *start = (TreeNode*) iptr->hashNodeChunk_;
    DbRetVal rc = OK;
    //int offset = info->fldOffset;

    //printDebug(DM_TreeIndex, "Inserting tree index node for  %s", iptr->indName_);
    //void *keyPtr =(void*)((char*)tuple + offset);
    if (!start)
    {
        //TODO::there is chance that two threads can insert first node at
        //same time causing the first tree node to leak.
        //printDebug(DM_TreeIndex, "\nInside if - start=NULL");
        Chunk *chunk = (Chunk*) iptr->chunkPtr_;
        TreeNode *tnode = (TreeNode*) chunk->allocate(tbl->getDB(), &rc);
        if (!tnode )
        {
            //printDebug(DM_TreeIndex, "\nExit TreeNode::Insert - 1 tnode=NULL");
            return rc;
        }
        tnode->mutex_.init();
        tnode->min_ = tuple;
        tnode->max_ = tuple;
        tnode->noElements_ =1;
        tnode->next_ = NULL;
        tnode->prev_ = NULL;
        tnode->balance_ = 0;
        char **rec = (char**)((char*) tnode + sizeof(TreeNode));
        printDebug(DM_TreeIndex, "\nStoring first record at %x\n", rec);
        *rec = (char*) tuple;
        iptr->hashNodeChunk_ = tnode;
    }else {
        rc = start->insert(tbl->getDB(), indInfo, indexPtr, tuple);
        //if (rc != OK)
        //    printError(rc, "Error in tree node insertion\n");
    }

    //printDebug(DM_TreeIndex, "\nExit TreeNode::Insert - 1");
    return rc;
}
void TreeNode::displayAll(int fldOffset)
{
    TreeNode *iter = this;
    int loc=0;
    while(iter->prev_)
    {
        printf("PRABA::ITERATING\n");
        iter = iter->prev_;
    }
    printf("\nDISPLAY NODES:START\n");
    while(iter != NULL)
    {
        char **rec = (char**)((char*) iter + sizeof(TreeNode));
        printf("\n>>>");
        for(loc=0;loc<iter->noElements_;loc++)
        {
            printf("%d,",*((int*)((char*) *(rec + loc )+fldOffset)));
        }
        iter = iter->next_;
    }
    printf("-----\n");
    printf("DISPLAY NODES:END\n");
}
void TreeNode::displayAll(IndexInfo *indInfo, void *indexPtr)
{
    HashIndexInfo *info = (HashIndexInfo*) indInfo;
    CINDEX *iptr = (CINDEX*)indexPtr;
    TreeNode *start = (TreeNode*) iptr->hashNodeChunk_;
    //int offset = info->fldOffset;
    //int noOfBuckets = info->noOfBuckets;
    TreeNode *iter =start;
    int loc=0;
    while(iter->prev_)
    {
        iter = iter->prev_;
    }
    printf("\nDISPLAY NODES:START\n");
    while(iter != NULL)
    {
        char **rec = (char**)((char*) iter + sizeof(TreeNode));
        printf("\n>>>");
        for(loc=0;loc<iter->noElements_;loc++)
        {
            printf("%d,",*((int*)((char*) *(rec + loc )+info->fldOffset)));
        }
        iter = iter->next_;
    }
    printf("-----\n");
    printf("DISPLAY NODES:END\n");
}
DbRetVal TreeNode::insert(Database *db, IndexInfo *indInfo, void *indexPtr, void *tuple)
{
    HashIndexInfo *info = (HashIndexInfo*) indInfo;
    CINDEX *iptr = (CINDEX*)indexPtr;
    TreeNode *start = (TreeNode*) iptr->hashNodeChunk_;
    //int offset = info->fldOffset;
;
    int noOfBuckets = info->noOfBuckets;
    TreeNode *iter =start; void *record = NULL;
    TreeNode *prev = start;
    //char *keyVal = (char*) tuple + info->fldOffset;
    //DbRetVal rc = OK;
    //bool recordInserted = false;
    //printDebug(DM_TreeIndex, "\nInside TreeNode::Insert - 2");
    //int count =0;
    int direction = 0;  //0:current,1:right,2:rightLeft,-1:left,-2:leftRight
    DbRetVal rv = OK;
    while(iter != NULL)
    {
        record = ((char*)iter->max_)+ info->fldOffset;
        //printDebug(DM_TreeIndex, "\n%d---%d", *((int*)keyVal), *((int*)record));
        bool result = 0;// AllDataType::compareVal(keyVal, record, OpGreaterThan,
                      //                        info->type, info->compLength);
        if (result)
        {
            if(direction == -1)
            {
                direction = -2;
                break;
            }
            direction = 1;
            prev = iter;
            iter = iter->next_;
            //printDebug(DM_TreeIndex, "\n2Insert- > ");
        }else
        {
            record = ((char*)iter->min_)+ info->fldOffset;
            result =0;// AllDataType::compareVal(keyVal, record, OpLessThan,
                      //                    info->type, info->compLength);
            if (result) {
                if(direction == 1)
                {
                    direction = 2;
                    break;
                }
                direction = -1;
                prev = iter;
                iter = iter->prev_;
                //printDebug(DM_TreeIndex, "\n2Insert- < ");
            }
            else
            {
                //printDebug(DM_TreeIndex, "\n2Insert- = ");
                direction=0;
                break;
            }
        }
    }

    if(direction == 2)
    {
        //Check the size of the prev node....
        //if not full then move the iter to prev and call insertLast()
        //else call insertFirst();

        if((iter->prev_ != NULL) && (iter->prev_->noElements_ < noOfBuckets) )
        {
            //printDebug(DM_TreeIndex, "\n2Insert- d=2 if ");
            iter = iter->prev_;
            rv  = insert(1, db, indInfo, iptr, tuple, iter);
        }
        else
        {
            //printDebug(DM_TreeIndex, "\n2Insert- d=2 else ");
            rv  = insert(-1, db, indInfo, iptr, tuple, iter);
        }
    }
    else if(direction == 1)
    {
        iter = prev;
        if((iter->noElements_ >= noOfBuckets) && (iter->next_ != NULL)
             && (iter->next_->noElements_ < noOfBuckets) )
        {
            //printDebug(DM_TreeIndex, "\n2Insert- d=1 if ");
            iter = iter->next_;
            rv  = insert(-1, db, indInfo, iptr, tuple, iter);
        }
        else
        {
            //printDebug(DM_TreeIndex, "\n2Insert- d=1 else ");
            rv = insert(1, db, indInfo, iptr, tuple, iter);
        }
    }
    else if(direction == -2)
    {
       if(iter->next_ != NULL && iter->next_->noElements_ < noOfBuckets )
       {
            //printDebug(DM_TreeIndex, "\n2Insert- d=-2 if ");
            iter = iter->next_;
            rv = insert(-1, db, indInfo, iptr, tuple, iter);
       }
       else
       {
           //printDebug(DM_TreeIndex, "\n2Insert- d=-2 else ");
           rv = insert(1, db, indInfo, iptr, tuple, iter);
       }
    }
    else if(direction == -1)
    {
        iter = prev;
        if((iter->noElements_ >= noOfBuckets) && (iter->prev_ != NULL)
            && (iter->prev_->noElements_ < noOfBuckets) )
        {
            //printDebug(DM_TreeIndex, "\n2Insert- d=-1 if ");
            iter = iter->prev_;
            rv = insert(1, db, indInfo, iptr, tuple, iter);
        }
       else
       {
           //printDebug(DM_TreeIndex, "\n2Insert- d=-1 else ");
           rv = insert(-1, db, indInfo, iptr, tuple, iter);
       }
    }
    else
    {
        //printDebug(DM_TreeIndex, "\n2Insert- d=0 ");
        rv = insert(0, db, indInfo, iptr, tuple, iter);
    }
    //printDebug(DM_TreeIndex, "\n %d While  ..Exit TreeNode::Insert - 2",count);
    return rv;
}
DbRetVal TreeNode::insert(int position, Database * db,
                          IndexInfo * indInfo,
                          CINDEX * iptr, void * tuple, TreeNode * iter)
{
    //position---  -1:First,0:Middle,1:Last
    HashIndexInfo *info = (HashIndexInfo*) indInfo;
    //TreeNode *start = (TreeNode*) iptr->hashNodeChunk_;
    //int offset = info->fldOffset;
    //enum_field_types  type = info->type;
    int noOfBuckets = info->noOfBuckets;
    void *record = NULL;
    //TreeNode *prev = start;
    //TreeNode *next = start;
    //char *keyVal = (char*) tuple + info->fldOffset;
    DbRetVal rc = OK;
    //bool recordInserted = false;
    iter->mutex_.getLock(db->procSlot);
    if(position == -1)
    {
        if(iter->noElements_ >= noOfBuckets)
        {
            Chunk *chunk = (Chunk*) iptr->chunkPtr_;
            TreeNode *tnode = (TreeNode*) chunk->allocate(db, &rc);
            if (tnode == NULL)
            {
                //printDebug(DM_TreeIndex, "\nExit TreeNode::Insert Position tnode=NULL");
                iter->mutex_.releaseLock(db->procSlot);
                return rc;
            }
            tnode->mutex_.init();
            tnode->min_ = tuple;
            tnode->max_ = tuple;
            tnode->noElements_ =1;
            tnode->next_ = iter;
            tnode->prev_ = iter->prev_;
            iter->prev_ = tnode;
            tnode->balance_ = 0;
            char **rec = (char**)((char*)tnode + sizeof(TreeNode));
            *rec = (char*) tuple;
        }
        else
        {
            //printDebug(DM_TreeIndex, "\n3Insert- p=-1 else ");
            char **rec = (char**)((char*)iter + sizeof(TreeNode));
            char *tmp = (char *)malloc(sizeof(void **) * iter->noElements_);
            memcpy(tmp, (char*)rec, sizeof(void **)* iter->noElements_);
            memcpy((char*)rec + sizeof(void **), tmp, sizeof(void **) * (iter->noElements_));
            free(tmp);
            iter->min_ = tuple;
            iter->noElements_++;
            *rec = (char*) tuple;
        }
    }
    else if(position == 1)
    {
        if(iter->noElements_ >= noOfBuckets)
        {
            //printDebug(DM_TreeIndex, "\n3Insert- p=1 if ");
            Chunk *chunk = (Chunk*) iptr->chunkPtr_;
            TreeNode *tnode = (TreeNode*) chunk->allocate(db, &rc);
            if (tnode == NULL)
            {
                //printDebug(DM_TreeIndex, "\nExit TreeNode::Insert Position tnode=NULL");
                iter->mutex_.releaseLock(db->procSlot);
                return rc;
            }
            tnode->mutex_.init();
            tnode->min_ = tuple;
            tnode->max_ = tuple;
            tnode->noElements_ =1;
            tnode->next_ = iter->next_;
            tnode->prev_ = iter;
            iter->next_ = tnode;
            if(tnode->next_)
            {
                tnode->next_->prev_ = tnode;
            }
            tnode->balance_ = 0;
            char **rec = (char**)((char*)tnode + sizeof(TreeNode));
            *rec = (char*) tuple;
        }
        else
        {
            //printDebug(DM_TreeIndex, "\n3Insert- p=1 else ");
            char **rec = (char**)((char*)iter + sizeof(TreeNode));
            rec = (char **)((char *)rec + (iter->noElements_ * sizeof(void **)));
            iter->max_ = tuple;
            iter->noElements_++;
            *rec = (char*) tuple;
            rec = (char**)((char*)iter + sizeof(TreeNode));
            rec = (char**)((char *)rec + ((iter->noElements_-1) * sizeof(void **)));
        }
    }
    else
    {
        //printDebug(DM_TreeIndex, "\n3Insert- p=0 ");

        int _start = 0;
        int end = iter->noElements_ - 1;
        int middle;
        int loc = 0;
        char **rec = (char**)((char*)iter + sizeof(TreeNode));
        //char *tmp = NULL;
        loc=0;
        for(middle = (_start + end) / 2; _start <= end ; middle = (_start +end )/2)
        {
            loc = middle;
            record = ((char*)*(rec+middle)) + info->fldOffset;
            //printDebug(DM_TreeIndex, "\n3Insert- p=0 get record \n");
            //printDebug(DM_TreeIndex, "%d-%d\n\n", *((int*)keyVal), *((int*)record));
            bool res = 0;//AllDataType::compareVal(keyVal, record, OpEquals, info->type, info->compLength);
            if(res)
            {
                loc = middle;
                if (info->isUnique) {
                    iter->mutex_.releaseLock(db->procSlot);
                    //printError(ErrUnique, "Unique constraint violation\n");
                    return ER_Unique;
                }
                break;
            }
            res = 0;//AllDataType::compareVal(keyVal, record, OpLessThan, info->type, info->compLength);
            if(res )
            {
                end = middle - 1;
            }
            else
            {
                _start = middle + 1;
                loc = _start;
            }
        }
        if(iter->noElements_ >= noOfBuckets)
        {
            //printDebug(DM_TreeIndex, "\n3Insert- p=0 if ");
                        Chunk *chunk = (Chunk*) iptr->chunkPtr_;
            TreeNode *tnode = (TreeNode*) chunk->allocate(db, &rc);
            if (tnode == NULL)
            {
                //printDebug(DM_TreeIndex, "\nExit TreeNode::Insert Position tnode=NULL");
                iter->mutex_.releaseLock(db->procSlot);
                return rc;
            }
            tnode->mutex_.init();
            tnode->next_ = iter->next_;
            tnode->prev_ = iter;
            iter->next_ = tnode;
            if(tnode->next_)
            {
                tnode->next_->prev_ = tnode;
            }
            tnode->balance_ = 0;
            char **_rec = (char**)((char*)iter + sizeof(TreeNode));
            char *tmp = (char *)malloc(sizeof(void *) * (iter->noElements_ - loc));
            memcpy(tmp, (char*)_rec + (loc * sizeof(void *)), sizeof(void *) * (iter->noElements_ - loc));/////////  Check the type cast char *
            _rec = (char**)((char *)_rec + (loc * sizeof(void *)));
            *_rec = (char*)tuple;
            tnode->noElements_ = iter->noElements_ - loc;
            iter->noElements_ = loc + 1;
            _rec = (char**)((char*)iter + sizeof(TreeNode));
            iter->min_ = *_rec;
            iter->max_ = tuple;
            _rec = (char**)((char*)tnode + sizeof(TreeNode));
            memcpy((char*)_rec, tmp, (tnode->noElements_) * sizeof(void *));
            tnode->min_ = *_rec;
            rec = (char**)((char *)rec + ((tnode->noElements_ - 1) * sizeof(void *)));
            tnode->max_ = *_rec ;
            free(tmp);
        }
        else
        {
            //printDebug(DM_TreeIndex, "\n3Insert- p=0 else pos-%d",loc);
            char **_rec = (char**)((char*)iter + sizeof(TreeNode));
            char *tmp = (char *)malloc(sizeof(void *) * (iter->noElements_ - loc));
            memcpy(tmp, (char*)_rec + (loc * sizeof(void *)), sizeof(void *) * (iter->noElements_ - loc));/////////  Check the type cast char *
            memcpy((char*)_rec + ((loc+1) * sizeof(void *)), tmp, sizeof(void *) * (iter->noElements_ - loc));
            free(tmp);
            if(loc==0)
            {
                iter->min_ = tuple;
            }
            iter->noElements_++;
            _rec = (char **)((char*)_rec + (loc * sizeof(void *)));
            *_rec = (char*)tuple;
        }
    }
    iter->mutex_.releaseLock(db->procSlot);
    return rc;
}

DbRetVal TreeIndex::remove(Table *tbl, Transaction *, void *indexPtr,
                           IndexInfo *indInfo, void *tuple,void*, bool )
{
    //printf("Tree index remove called\n");
    HashIndexInfo *info = (HashIndexInfo*) indInfo;
    CINDEX *iptr = (CINDEX*)indexPtr;
    TreeNode *start = (TreeNode*) iptr->hashNodeChunk_;
    TreeNode *iter = locateNode(start, tuple, indInfo);
    if (NULL == iter) return OK; //element not found
    removeElement(tbl->getDB(), iter, tuple, info);
    return OK;
}
TreeNode* TreeIndex::locateNode(TreeNode *iter, void *, IndexInfo *indInfo)
{
    HashIndexInfo *info = (HashIndexInfo*) indInfo;
    //void *searchKey =(void*)((char*)tuple + info->fldOffset);
    while(iter != NULL)
    {
        char *record = ((char*)iter->max_)+ info->fldOffset;
        bool result =0;// AllDataType::compareVal(searchKey, record,
                       //                       OpGreaterThan,
                       //                       info->type, info->compLength);
        if (result)
        {
            iter = iter->next_;
        }else
        {
            record = ((char*)iter->min_)+ info->fldOffset;
            result = 0;//AllDataType::compareVal(searchKey, record,
                       //                      OpGreaterThanEquals,
                        //                     info->type, info->compLength);
            if (result) {
               //current node contains the key
               return iter;
            }
            else
            {
               //need to move left
               iter = iter->prev_;
            }
        }
    }
    return NULL;
}
DbRetVal TreeIndex::removeElement(Database *db, TreeNode *iter, void *tuple,
                                  HashIndexInfo *)
{
    //void *searchKey =(void*)((char*)tuple + info->fldOffset);
    int loc=0, middle=0, start=0, end=iter->noElements_-1;
    char **rec = (char**)((char*)iter + sizeof(TreeNode));
    iter->mutex_.getLock(db->procSlot);
    for(middle = (start + end) / 2; start <= end ; middle = (start +end )/2)
    {
        loc = middle;
        //char *record = ((char*)*(rec+middle)) + info->fldOffset;
        bool res = 0;//AllDataType::compareVal(searchKey, record, OpEquals,
                   //                        info->type, info->compLength);
        if(res)
        {
            loc = middle;
            break;
        }
        //res = AllDataType::compareVal(searchKey, record, OpLessThan,
                                       //   info->type, info->compLength);
        if(res)
        {
            end = middle - 1;
        }
        else
        {
            start = middle + 1;
            loc = start;
        }
    }
    char *tmp = (char *)malloc(sizeof(void *) * (iter->noElements_ - loc));
    memcpy(tmp, (char*)rec + ((loc+1) * sizeof(void *)), sizeof(void *) * (iter->noElements_ - loc));
    memcpy((char*)rec + ((loc) * sizeof(void *)), tmp, sizeof(void *) * (iter->noElements_ - loc));
    free(tmp);
    if(loc==0)
    {
       iter->min_ = tuple;
    }
    iter->mutex_.releaseLock(db->procSlot);
    //TODO::if noElement is zero then deallocate the tree node
    iter->noElements_--;
    return OK;
}


DbRetVal TreeIndex::update(Table* , Transaction *, void *,
                           IndexInfo *, void *, bool )
{
    //CINDEX *iptr = (CINDEX*)indexPtr;

    //HashIndexInfo *info = (HashIndexInfo*) indInfo;
    //check whether the index key is updated or not
    //if it is not updated return from here
    bool keyNotUpdated = false;
    //M_FieldIterator idxFldIter = info->idxFldList.getIterator();
    /*
    while (idxFldIter.hasElement())
    {
        m_field_def *idef = idxFldIter.nextElement();
        FieldIterator fldIter = tbl->fldList_.getIterator();
        while (fldIter.hasElement())
        {
            FieldDef *def = fldIter.nextElement();
            if (0 == strcmp(def->fldName_, idef->fldName_))
            {
                if (NULL != def->bindVal_)
                {
                    //Not Implemented
                    return ErrNotYet;
                }
               keyNotUpdated = true;
               break;
            }
        }
    }*/
    if (keyNotUpdated)
    {
        return OK;
    }
    return ER_NotYet;
}

